package com.zhu.algorithm.sort;


import com.zhu.algorithm.sort.impl.Sort;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zhujiabao
 * @Date: 2021/12/23/20:09
 * @Description:选择排序
 *
 * 算法步骤
 * 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
 *
 * 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
 *
 * 重复第二步，直到所有元素均排序完毕。
 */
public class SelectionSort implements Sort {

    @Override
    public int[] sort(int[] sourceArray){
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        long A=System.currentTimeMillis();

        for (int i=0; i<arr.length; i++){
            int k = i;
            for (int j=i+1; j<arr.length; j++){
                if (arr[k]>arr[j]){
                    k=j;
                }
            }

            int temp = arr[i];
            arr[i] = arr[k];
            arr[k] = temp;
        }

        long B=System.currentTimeMillis();
        System.out.println("选择排序所耗时间： "+(B-A)+"ms");

        return arr;
    }
}
